package com.rising.face.ali.bishi.findmaxstr;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: rising
 * @Description: 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
 * 示例 1:
 * 输入: "abcabcbb"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
 *
 * 示例 2:
 * 输入: "bbbbb"
 * 输出: 1
 * 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
 *
 * 示例 3:
 * 输入: "pwwkew"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
 * 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
 * @Date: create in 2021/2/8 20:35
 */
public class FindMaxLengthStr {

    public static void main(String[] args) {
        System.out.println(findMaxStr("abcabcbb") + "------" + lengthOfLongestSubstring("abcabcbb"));//abc 3
        System.out.println(findMaxStr("bbbbb") + "------" + lengthOfLongestSubstring("bbbbb"));//b 1
        System.out.println(findMaxStr("pwwkew") + "------" + lengthOfLongestSubstring("pwwkew"));//wke 3
        System.out.println(findMaxStr("abccffghjk") + "------" + lengthOfLongestSubstring("abccffghjk"));//fghjk 5
        System.out.println(findMaxStr("dvdf")+ "------" + lengthOfLongestSubstring("dvdf"));//vdf 3
    }

    public static int findMaxStr(String str) {
        char[] chars = str.toCharArray();
        int max = 0;//最大值
        int num = 0;//当前子串的长度
        Map<Character,Integer> reMap = new HashMap<>();//存放每次不重复的数据
        for (int i = 0; i < str.length(); i++) {
            if (reMap.get(chars[i]) != null){//说明此时map已经有个重复数据，则此次终结。
                max = num >= max ? num:max;
                num = 0;
                //指针回退，需要判定回退哪个位置
                for (int index = i - 1; index >= 0; index--) {
                    if (chars[index] == chars[i]) {
                        i = index;
                        break;
                    }
                }
                reMap.clear();
                continue;
            }
            //map中没有重复数据，则此时子串长度加1.
            num++;
            //将当前字符串放到map中
            reMap.put(chars[i], i);
        }
        //比较最大值和最后计算出来的长度，谁大返回谁
        max = num >= max ? num:max;
        return max;
    }

    public static int lengthOfLongestSubstring(String s) {
        char[] chars = s.toCharArray();
        int max = 0;//最大值
        int num = 0;//当前子串的长度
        Map<Character,Integer> reMap = new HashMap<>();//存放每次不重复的数据
        for (int i = 0; i < s.length(); i++) {
            if (reMap.get(chars[i]) != null){//说明此时map已经有个重复数据，则此次终结。
                max = num >= max ? num:max;
                num = 0;
                //指针回退，需要判定回退哪个位置
                for (int index = i - 1; index >= 0; index--) {
                    if (chars[index] == chars[i]) {
                        i = index;
                        break;
                    }
                }
                reMap.clear();
                continue;
            }
            //map中没有重复数据，则此时子串长度加1.
            num++;
            //将当前字符串放到map中
            reMap.put(chars[i], i);
        }
        //比较最大值和最后计算出来的长度，谁大返回谁
        max = num >= max ? num:max;
        return max;
    }

}
